home *** CD-ROM | disk | FTP | other *** search
/ Visual Cafe 3 / Visual Cafe 3.ISO / Vcafe / Main.bin / BitSet.java < prev    next >
Text File  |  1998-09-22  |  9KB  |  335 lines
  1. /*
  2.  * @(#)BitSet.java    1.27 98/07/01
  3.  *
  4.  * Copyright 1995-1998 by Sun Microsystems, Inc.,
  5.  * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A.
  6.  * All rights reserved.
  7.  * 
  8.  * This software is the confidential and proprietary information
  9.  * of Sun Microsystems, Inc. ("Confidential Information").  You
  10.  * shall not disclose such Confidential Information and shall use
  11.  * it only in accordance with the terms of the license agreement
  12.  * you entered into with Sun.
  13.  */
  14.  
  15. package java.util;
  16.  
  17. /**
  18.  * A set of bits. The set automatically grows as more bits are needed. 
  19.  *
  20.  * @version     1.27, 07/01/98
  21.  * @author Arthur van Hoff
  22.  */
  23. public final class BitSet implements Cloneable, java.io.Serializable {
  24.     private final static int BITS_PER_UNIT = 6;
  25.     private final static int MASK = (1<<BITS_PER_UNIT)-1;
  26.     private long bits[];
  27.  
  28.     /**
  29.      * Convert bitIndex to a subscript into the bits[] array.
  30.      */
  31.     private static int subscript(int bitIndex) {
  32.     return bitIndex >> BITS_PER_UNIT;
  33.     }
  34.     /**
  35.      * Convert a subscript into the bits[] array to a (maximum) bitIndex.
  36.      */
  37.     private static int bitIndex(int subscript) {
  38.     return (subscript << BITS_PER_UNIT) + MASK;
  39.     }
  40.  
  41.     private static boolean debugging = (System.getProperty("debug") != null);
  42.  
  43.     /** use serialVersionUID from JDK 1.0.2 for interoperability */
  44.     private static final long serialVersionUID = 7997698588986878753L;
  45.  
  46.     /**
  47.      * Creates an empty set.
  48.      */
  49.     public BitSet() {
  50.     this(1 << BITS_PER_UNIT);
  51.     }
  52.  
  53.     /**
  54.      * Creates an empty set with the specified size.
  55.      * @param nbits the size of the set
  56.      */
  57.     public BitSet(int nbits) {
  58.     /* nbits can't be negative; size 0 is OK */
  59.     if (nbits < 0) {
  60.         throw new NegativeArraySizeException(Integer.toString(nbits));
  61.     }
  62.     /* On wraparound, truncate size; almost certain to o-flo memory. */
  63.     if (nbits + MASK < 0) {
  64.         nbits = Integer.MAX_VALUE - MASK;
  65.     }
  66.     /* subscript(nbits + MASK) is the length of the array needed to hold nbits */
  67.     bits = new long[subscript(nbits + MASK)];
  68.     }
  69.  
  70.     /**
  71.      * Ensures that the BitSet can hold at least an nth bit.
  72.      * This cannot leave the bits array at length 0.
  73.      * @param    nth    the 0-origin number of the bit to ensure is there.
  74.      */
  75.     private void ensureCapacity(int nth) {
  76.     /* Doesn't need to be synchronized because it's an internal method. */
  77.     int required = subscript(nth) + 1;    /* +1 to get length, not index */
  78.     if (required > bits.length) {
  79.         /* Ask for larger of doubled size or required size */
  80.         int request = Math.max(2 * bits.length, required);
  81.         long newBits[] = new long[request];
  82.         System.arraycopy(bits, 0, newBits, 0, bits.length);
  83.         bits = newBits;
  84.     }
  85.     }
  86.  
  87.     /**
  88.      * Sets a bit.
  89.      * @param bit the bit to be set
  90.      */
  91.     public void set(int bit) {
  92.     if (bit < 0) {
  93.         throw new IndexOutOfBoundsException(Integer.toString(bit));
  94.     }
  95.     synchronized (this) {
  96.         ensureCapacity(bit);
  97.         bits[subscript(bit)] |= (1L << (bit & MASK));
  98.     }
  99.     }
  100.  
  101.     /**
  102.      * Clears a bit.
  103.      * @param bit the bit to be cleared
  104.      */
  105.     public void clear(int bit) {
  106.     if (bit < 0) {
  107.         throw new IndexOutOfBoundsException(Integer.toString(bit));
  108.     }
  109.     synchronized (this) {
  110.         ensureCapacity(bit);
  111.         bits[subscript(bit)] &= ~(1L << (bit & MASK));
  112.     }
  113.     }
  114.  
  115.     /**
  116.      * Gets a bit.
  117.      * @param bit the bit to be gotten
  118.      */
  119.     public boolean get(int bit) {
  120.     if (bit < 0) {
  121.         throw new IndexOutOfBoundsException(Integer.toString(bit));
  122.     }
  123.     boolean result = false;
  124.     synchronized (this) {
  125.         int n = subscript(bit);        /* always positive */
  126.         if (n < bits.length) {
  127.         result = ((bits[n] & (1L << (bit & MASK))) != 0);
  128.         }
  129.     }
  130.     return result;
  131.     }
  132.  
  133.     /**
  134.      * Logically ANDs this bit set with the specified set of bits.
  135.      * @param set the bit set to be ANDed with
  136.      */
  137.     public void and(BitSet set) {
  138.     /*
  139.      * Need to synchronize  both this and set.
  140.      * This might lead to deadlock if one thread grabs them in one order
  141.      * while another thread grabs them the other order.
  142.      * Use a trick from Doug Lea's book on concurrency,
  143.      * somewhat complicated because BitSet overrides hashCode().
  144.      */
  145.     if (this == set) {
  146.         return;
  147.     }
  148.     BitSet first = this;
  149.     BitSet second = set;
  150.     if (System.identityHashCode(first) > System.identityHashCode(second)) {
  151.         first = set;
  152.         second = this;
  153.     }
  154.     synchronized (first) {
  155.         synchronized (second) {
  156.         int bitsLength = bits.length;
  157.         int setLength = set.bits.length;
  158.         int n = Math.min(bitsLength, setLength);
  159.         for (int i = n ; i-- > 0 ; ) {
  160.             bits[i] &= set.bits[i];
  161.         }
  162.         for (; n < bitsLength ; n++) {
  163.             bits[n] = 0;
  164.         }
  165.         }
  166.     }
  167.     }
  168.  
  169.     /**
  170.      * Logically ORs this bit set with the specified set of bits.
  171.      * @param set the bit set to be ORed with
  172.      */
  173.     public void or(BitSet set) {
  174.     if (this == set) {
  175.         return;
  176.     }
  177.     /* See the note about synchronization in and(), above. */
  178.     BitSet first = this;
  179.     BitSet second = set;
  180.     if (System.identityHashCode(first) > System.identityHashCode(second)) {
  181.         first = set;
  182.         second = this;
  183.     }
  184.     synchronized (first) {
  185.         synchronized (second) {
  186.         int setLength = set.bits.length;
  187.         if (setLength > 0) {
  188.             ensureCapacity(bitIndex(setLength-1));
  189.         }
  190.         for (int i = setLength; i-- > 0 ;) {
  191.             bits[i] |= set.bits[i];
  192.         }
  193.         }
  194.     }
  195.     }
  196.  
  197.     /**
  198.      * Logically XORs this bit set with the specified set of bits.
  199.      * @param set the bit set to be XORed with
  200.      */
  201.     public void xor(BitSet set) {
  202.     /* See the note about synchronization in and(), above. */
  203.     BitSet first = this;
  204.     BitSet second = set;
  205.     if (System.identityHashCode(first) > System.identityHashCode(second)) {
  206.         first = set;
  207.         second = this;
  208.     }
  209.     synchronized (first) {
  210.         synchronized (second) {
  211.         int setLength = set.bits.length;
  212.         if (setLength > 0) {
  213.             ensureCapacity(bitIndex(setLength-1));
  214.         }
  215.         for (int i = setLength; i-- > 0 ;) {
  216.             bits[i] ^= set.bits[i];
  217.         }
  218.         }
  219.     }
  220.     }
  221.  
  222.     /**
  223.      * Gets the hashcode.
  224.      */
  225.     public int hashCode() {
  226.     long h = 1234;
  227.     synchronized (this) {
  228.         for (int i = bits.length; --i >= 0; ) {
  229.         h ^= bits[i] * (i + 1);
  230.         }
  231.     }
  232.     return (int)((h >> 32) ^ h);
  233.     }
  234.     
  235.     /**
  236.      * Calculates and returns the set's size in bits.
  237.      * The maximum element in the set is the size - 1st element.
  238.      */
  239.     public int size() {
  240.     /* This doesn't need to be synchronized, since it just reads a field. */
  241.     return bits.length << BITS_PER_UNIT;
  242.     }
  243.  
  244.     /**
  245.      * Compares this object against the specified object.
  246.      * @param obj the object to compare with
  247.      * @return true if the objects are the same; false otherwise.
  248.      */
  249.     public boolean equals(Object obj) {
  250.     if ((obj != null) && (obj instanceof BitSet)) {
  251.         if (this == obj) {
  252.         return true;
  253.         }
  254.         BitSet set = (BitSet) obj;
  255.         /* See the note about synchronization in and(), above. */
  256.         BitSet first = this;
  257.         BitSet second = set;
  258.         if (System.identityHashCode(first) > System.identityHashCode(second)) {
  259.         first = set;
  260.         second = this;
  261.         }
  262.         synchronized (first) {
  263.         synchronized (second) {
  264.             int bitsLength = bits.length;
  265.             int setLength = set.bits.length;
  266.             int n = Math.min(bitsLength, setLength);
  267.             for (int i = n ; i-- > 0 ;) {
  268.             if (bits[i] != set.bits[i]) {
  269.                 return false;
  270.             }
  271.             }
  272.             if (bitsLength > n) {
  273.             for (int i = bitsLength ; i-- > n ;) {
  274.                 if (bits[i] != 0) {
  275.                 return false;
  276.                 }
  277.             }
  278.             } else if (setLength > n) {
  279.             for (int i = setLength ; i-- > n ;) {
  280.                 if (set.bits[i] != 0) {
  281.                 return false;
  282.                 }
  283.             }
  284.             }
  285.         }
  286.         }
  287.         return true;
  288.     }
  289.     return false;
  290.     }
  291.  
  292.     /**
  293.      * Clones the BitSet.
  294.      */
  295.     public Object clone() {
  296.     BitSet result = null;
  297.     synchronized (this) {
  298.         try {
  299.         result = (BitSet) super.clone();
  300.         } catch (CloneNotSupportedException e) {
  301.         // this shouldn't happen, since we are Cloneable
  302.         throw new InternalError();
  303.         }
  304.         result.bits = new long[bits.length];
  305.         System.arraycopy(bits, 0, result.bits, 0, result.bits.length);
  306.     }
  307.     return result;
  308.     }
  309.  
  310.     /**
  311.      * Converts the BitSet to a String.
  312.      */
  313.     public String toString() {
  314.     StringBuffer buffer = new StringBuffer();
  315.     boolean needSeparator = false;
  316.     buffer.append('{');
  317.     synchronized (this) {
  318.         int limit = size();
  319.         for (int i = 0 ; i < limit ; i++) {
  320.         if (get(i)) {
  321.             if (needSeparator) {
  322.             buffer.append(", ");
  323.             } else {
  324.             needSeparator = true;
  325.             }
  326.             buffer.append(i);
  327.         }
  328.         }
  329.     }
  330.     buffer.append('}');
  331.     return buffer.toString();
  332.     }
  333. }
  334.  
  335.